package com.s9.hashtable1;

/**
 * 散列表实现：如果不存在则插入队尾【队伍满了则删除 head 元素】，否则存在则拔出之后继续插入队尾
 */
public class HashTable<K, V> {

	/**
	 * 散列表默认长度
	 */
	private static final int DEFAULT_INITAL_CAPACITY = 8;

	/**
	 * 装载因子
	 */
	private static final float LOAD_FACTOR = 0.75F;

	/**
	 * 初始化散列表数组
	 */
	private Entry<K, V>[] table;

	/**
	 * 实际元素数量
	 */
	private int size = 0;

	/**
	 * 散列表索引数量
	 */
	private int use = 0;

	@SuppressWarnings("unchecked")
	public HashTable() {
		table = (Entry<K, V>[]) new Entry[DEFAULT_INITAL_CAPACITY];
	}

	static final class Entry<K, V> {
		K key;

		V value;

		Entry<K, V> next;

		Entry(K key, V value, Entry<K, V> next) {
			this.key = key;
			this.value = value;
			this.next = next;
		}
	}

	/**
	 * 新增
	 * 
	 * @param key
	 * @param value
	 */
	public void put(K key, V value) {
		int index = this.hash(key);
		// 位置未被引用，创建哨兵节点
		if (table[index] == null) {
			table[index] = new Entry<>(null, null, null);
		}

		Entry<K, V> tmp = table[index];
		// 新增节点
		if (tmp.next == null) {
			tmp.next = new Entry<>(key, value, null);
			this.size++;
			this.use++;
			// 动态扩容
			if (this.use >= table.length * LOAD_FACTOR) {
				resize();
			}
		}
		// 解决散列冲突，使用链表法
		else {
			do {
				tmp = tmp.next;
				// key相同，覆盖旧的数据
				if (tmp.key == key) {
					tmp.value = value;
					return;
				}
			} while (tmp.next != null);
			// 插入链表的头部
			Entry<K, V> temp = table[index].next;
			table[index].next = new Entry<>(key, value, temp);
			size++;
		}
	}

	/**
	 * 散列函数
	 * <p>
	 * 参考 hashmap 散列函数
	 * 
	 * @param key
	 * @return
	 */
	private int hash(Object key) {
		int h;
		return (key == null) ? 0 : ((h = key.hashCode()) ^ (h >>> 16))
				% table.length;
	}

	/**
	 * 扩容
	 */
	@SuppressWarnings("unchecked")
	private void resize() {
		Entry<K, V>[] oldTable = this.table;
		this.table = (Entry<K, V>[]) new Entry[table.length * 2];
		this.use = 0;
		for (int i = 0; i < oldTable.length; i++) {
			if (oldTable[i] == null || oldTable[i].next == null) {
				continue;
			}
			Entry<K, V> e = oldTable[i];
			// 该位置包含有效元素
			while (e.next != null) {
				e = e.next;
				int index = this.hash(e.key);
				if (table[index] == null) {
					this.use++;
					// 创建哨兵节点
					this.table[index] = new Entry<>(null, null, null);
				}
				this.table[index].next = new Entry<>(e.key, e.value,
						this.table[index].next);
			}
		}
	}

	/**
	 * 删除
	 * 
	 * @param key
	 */
	public void remove(K key) {
		int index = hash(key);
		Entry<K, V> e = table[index];
		// 该位置没有值 或者 只有头结点则表示 查无此 entry
		if (e == null || e.next == null) {
			return;
		}

		Entry<K, V> pre;
		Entry<K, V> headNode = table[index];
		do {
			pre = e;
			e = e.next;
			if (key == e.key) {
				pre.next = e.next;
				size--;
				if (headNode.next == null)
					use--;
				return;
			}
		} while (e.next != null);
	}

	/**
	 * 获取
	 * 
	 * @param key
	 * @return
	 */
	public V get(K key) {
		int index = hash(key);
		Entry<K, V> e = table[index];
		if (e == null) {
			return null;
		}
		while (e.next != null) {
			e = e.next;
			if (key == e.key) {
				return e.value;
			}
		}
		return null;
	}

	@Override
	public String toString() {
		int max = this.size - 1;
		if (max == -1)
			return "{}";

		StringBuilder sb = new StringBuilder();
		sb.append('{');

		int i = 0;
		Entry<K, V>[] tab = (Entry<K, V>[]) table;
		for (Entry<K, V> entry : tab) {
			if (entry == null) {
				continue;
			}
			while (entry.next != null) {
				entry = entry.next;
				K key = entry.key;
				V value = entry.value;
				sb.append(key == this ? "(this Map)" : key.toString());
				sb.append('=');
				sb.append(value == this ? "(this Map)" : value.toString());

				if (++i == this.size) {
					sb.append('}');
				} else {
					sb.append(", ");
				}
			}
		}
		return sb.toString();
	}
}
